package hyy_2022;

import commons.ListNode;

public class _0708_21_MergeTwoLists {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(2);
        ListNode list3 = new ListNode(4);
        list1.next = list2;
        list2.next = list3;

        ListNode list4 = new ListNode(1);
        ListNode list5 = new ListNode(3);
        ListNode list6 = new ListNode(4);
        list4.next = list5;
        list5.next = list6;

        ListNode mergeNode = mergeTwoLists(list1,list4);
        while(mergeNode != null) {
            System.out.println(mergeNode.val);
            mergeNode = mergeNode.next;
        }
    }

    /**
     * 合并链表
     * @param list1 链表1
     * @param list2 链表2
     * @return ListNode 合并后的链表头结点
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //prehead设计精妙,我咋就想不到呢
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            //关键一步，prev指向新加结点上
            prev = prev.next;
        }

        //合并后, list1 和 list2 最多有一个没合并完 , 直接将链表末尾指向未合并完的链表即可
        prev.next = list1 == null ? list2 : list1;

        return prehead.next;
    }
}


